package problem70_Climbing_Stairs;

public class MySolution {
	public int climbStairs(int n) {
		int sum=0,numOfOne=n;
		//numOfOne=n,numOfOne=n-2,
		while(numOfOne>=0){
			int numOfTwo=(n-numOfOne)/2;
			sum+=factorial(numOfOne+numOfTwo)/(factorial(numOfTwo)*factorial(numOfOne));
			numOfOne-=2;
		}
		return sum;
	}
	
	private long factorial(int n){
		if(n==0) return 1;
		long result=1;
		for(long i=1;i<=n;i++){
			result*=i;
		}
		System.out.println("factorial "+n+" :"+result);
		return result;
	}
	
	public static void main(String[] args){
		System.out.println(new MySolution().climbStairs(30));
	}
}
